//给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 
//
// 可以假设除了数字 0 之外，这两个数字都不会以零开头。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：l1 = [7,2,4,3], l2 = [5,6,4]
//输出：[7,8,0,7]
// 
//
// 示例 2： 
//
// 
//输入：l1 = [2,4,3], l2 = [5,6,4]
//输出：[8,0,7]
// 
//
// 示例 3： 
//
// 
//输入：l1 = [0], l2 = [0]
//输出：[0]
// 
//
// 
//
// 提示： 
//
// 
// 链表的长度范围为 [1, 100] 
// 0 <= node.val <= 9 
// 输入数据保证链表代表的数字无前导 0 
// 
//
// 
//
// 进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。 
//
// 
//
// 
// 注意：本题与主站 445 题相同：https://leetcode-cn.com/problems/add-two-numbers-ii/ 
//
// Related Topics 栈 链表 数学 👍 109 👎 0


package LeetCode.editor.cn;


import java.util.ArrayDeque;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-04-11 10:21:19
 * @description LCR 025.两数相加 II
 
 */
 
public class LMSNwu {
    public static void main(String[] args) {
    //测试代码
    LMSNwu fun = new LMSNwu();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)

//  Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
        //递归或者栈
    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        ArrayDeque<ListNode> st1=new ArrayDeque<>();
        ArrayDeque<ListNode> st2=new ArrayDeque<>();
        while (l1!=null){
            st1.push(l1);
            l1=l1.next;
        }
        while (l2!=null){
            st2.push(l2);
            l2=l2.next;
        }
        ListNode res=new ListNode(-1);
        ListNode pre=null;
        int p=0;
        while (!st1.isEmpty()||!st2.isEmpty()){
            int o1=0,o2=0;
            if(!st1.isEmpty()){
                o1=st1.pop().val;
            }
            if(!st2.isEmpty()){
                o2=st2.pop().val;
            }
            int t=(o1+o2+p)%10;
            p=(o1+o2+p)/10;
            ListNode next = new ListNode(t);
            next.next=res.next;
            res.next= next;
        }
        if(p!=0) {
            ListNode listNode = new ListNode(1);
            listNode.next=res.next;
            return listNode;
        }
        return res.next;
    }
    //递归反转链表后相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2); // l1 和 l2 反转后，就变成【2. 两数相加】了
        ListNode l3 = addTwo(l1, l2, 0);
        return reverseList(l3);
    }

    private ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head; // 把下一个节点指向自己
        head.next = null; // 断开指向下一个节点的连接，保证最终链表的末尾节点的 next 是空节点
        return newHead;
    }

    // l1 和 l2 为当前遍历的节点，carry 为进位
    private ListNode addTwo(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null) { // 递归边界：l1 和 l2 都是空节点
            return carry != 0 ? new ListNode(carry) : null; // 如果进位了，就额外创建一个节点
        }
        if (l1 == null) { // 如果 l1 是空的，那么此时 l2 一定不是空节点
            l1 = l2;
            l2 = null; // 交换 l1 与 l2，保证 l1 非空，从而简化代码
        }
        carry += l1.val + (l2 != null ? l2.val : 0); // 节点值和进位加在一起
        l1.val = carry % 10; // 每个节点保存一个数位
        l1.next = addTwo(l1.next, (l2 != null ? l2.next : null), carry / 10); // 进位
        return l1;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
